Theo định nghĩa, với mọi bài toán trong RP, tồn tại thuật toán sao cho nếu lời giải trả về là Có thì thuật toán luôn đúng và nếu lời giải trả về là Không thì thuật toán thường đúng. Lớp co-RP được định nghĩa tương tự như vậy, nhưng với các thuật toán co-RP, lời giải Không luôn đúng và lời giải Có thường đúng. Nói cách khác, thuật toán chấp nhận mọi trường hợp Có nhưng có thể chấp nhận hoặc từ chối các trường hợp Không. Lớp BPP gồm các bài toán có thuật toán thường đúng nhưng được phép trả lời sai với xác suất thấp trong cả hai trường hợp, và do đó là tập hợp cha của cả RP và co-RP. Giao của RP và co-RP là lớp ZPP.